package LeetCode._02算法基础.day04双指针;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 14 - 17:07
 * @Description 给定两个由一些 闭区间 组成的列表
 * 每个区间列表都是成对 不相交 的，并且 已经排序 。
 * 返回这 两个区间列表的交集 。
 * 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。
 * 例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
 * [1,3] 和 [3,4] 的交集为 [3, 3]
 * @Version 中等
 */
public class _986区间列表的交集 {
    static int[][] firstList = {
            {0, 2},{5, 10},{13,23},{24,25}
    };
    static int[][] secondList = {
            {1,5},{8,12},{15,24},{15,24}
    };
    @Test
    public void solve(){
        int[][] res = intervalIntersection(firstList, secondList);
        for(int[] row : res){
            System.out.println(row[0] + "\t" + row[1]);
        }
    }
    /*by me 双指针（时空复杂度高）*/
    //两个列表的区间逐一比较
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        int[] interval1, interval2;
        while (i < firstList.length && j < secondList.length) {
            interval1 = firstList[i];
            interval2 = secondList[j];
            //firstList 第i个区间左端 比 secondList 第j个区间 右端大
            if (interval1[0] > interval2[1]) {
                j++;
                continue;
            }
            //secondList 第j个区间左端 比 firstList 第i个区间 右端大
            if (interval2[0] > interval1[1]) {
                i++;
                continue;
            }
            //firstList 第i个区间右端 介于 secondList 第j个区间
            if (interval1[1] >= interval2[0] && interval1[1] <= interval2[1]) {
                result.add(new int[]{Math.max(interval1[0], interval2[0]), interval1[1]});
                i++;
                continue;
            }
            //secondList 第j个区间右端 介于 firstList 第i个区间
            if (interval2[1] >= interval1[0] && interval2[1] <= interval1[1]) {
                result.add(new int[]{Math.max(interval1[0], interval2[0]), interval2[1]});
                j++;
            }
        }

        return result.toArray(new int[result.size()][]);
    }

    /*官方思路*/
    //归并区间
    public int[][] intervalIntersection1(int[][] A, int[][] B) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, j = 0;

        while (i < A.length && j < B.length) {
            // Let's check if A[i] intersects B[j].
            // lo - the startpoint of the intersection
            // hi - the endpoint of the intersection
            int lo = Math.max(A[i][0], B[j][0]);
            int hi = Math.min(A[i][1], B[j][1]);
            if (lo <= hi)
                ans.add(new int[]{lo, hi});

            // Remove the interval with the smallest endpoint
            if (A[i][1] < B[j][1])
                i++;
            else
                j++;
        }

        return ans.toArray(new int[ans.size()][]);
    }
}
